/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package expression;

import java.util.List;
import java.util.Scanner;

/**
 *
 * @author dlao
 */
public class Expression {

//    // Root node pointer. Will be null for an empty tree. 
    private Node root;
    private Node n21;
//
//
//    /* 
//    --Node-- 
//    The binary tree is built using this nested node class. 
//    Each node stores one data element, and has left and right 
//    sub-tree pointer which may be null. 
//    The node is a "dumb" nested class -- we just use it for 
//    storage; it does not have any methods. 
//     */

    private static class Node {

        Node left;
        Node right;
        int data;

        Node(int newData) {
            left = null;
            right = null;
            data = newData;
        }
    }
//
//    /** 
//    Creates an empty binary tree -- a null root pointer. 
//     */

    public void Expression() {
        root = null;
        n21 = null;
    }
//
//    /** 
//    Returns true if the given target is in the binary tree. 
//    Uses a recursive helper. 
//     */

    public boolean lookup(int data) {
        return (lookup(root, data));
    }
//
//    /** 
//    Recursive lookup  -- given a node, recur 
//    down searching for the given data. 
//     */

    private boolean lookup(Node node, int data) {
        if (node == null) {
            System.out.println("false");
            return (false);
        }

        if (data == node.data) {
            System.out.println("true " + node.data);
            return (true);
        } else if (data < node.data) {
            System.out.println("data < node.data: " + node.data);
            return (lookup(node.left, data));
        } else {
            System.out.println("data > node.data: " + node.data);
            return (lookup(node.right, data));
        }
    }
//
//    /** 
//    Inserts the given data into the binary tree. 
//    Uses a recursive helper. 
//     */

    public void insert(int data) {
        root = insert(root, data);
    }
//
//    /** 
//    Recursive insert -- given a node pointer, recur down and 
//    insert the given data into the tree. Returns the new 
//    node pointer (the standard way to communicate 
//    a changed pointer back to the caller). 
//     */

    private Node insert(Node node, int data) {
        if (node == null) {
            node = new Node(data);
            //System.out.println("node = null, node insert data: " + data);
        } else {
            if (data <= node.data) {
               // System.out.println("data <= " + node.data + "; node.left insert data: " + data);
                node.left = insert(node.left, data);

            } else {
               // System.out.println("data >= " + node.data + "; node.right insert data: " + data);
                node.right = insert(node.right, data);

            }
        }

        return (node); // in any case, return the new pointer to the caller 
    }

    public void printPostorder() {
        printPostorder(root);
        System.out.println();
    }

    public void printPostorder(Node node) {
        if (node == null) {
            return;
        }

        // first recur on both subtrees 
        printPostorder(node.left);
        printPostorder(node.right);

        // then deal with the node 
        System.out.print(node.data + "  ");
    }

    public void build123b() {

        // root = null;
        root = insert(root, 65);
        root = insert(root, 20);
        root = insert(root, 57);

        // Node n21 = null;
        root = insert(root, 82);
        root = insert(root, 77);
        root = insert(root, 85);
//        root = insert(root, 7);
//        root = insert(root, 5);
//        root = insert(root, 20);
//          root = new Node(2);
//        Node n11 = new Node(7);
//        Node n12 = new Node(5);


//        Node n21 = new Node(2);
//        Node n22 = new Node(6);
//        Node n23 = new Node(3);
//        Node n24 = new Node(6);
//        Node n31 = new Node(5);
//        Node n32 = new Node(8);
//        Node n33 = new Node(4);
//        Node n34 = new Node(5);
//        Node n35 = new Node(8);
//        Node n36 = new Node(4);
//        Node n37 = new Node(5);
//        Node n38 = new Node(8);

//         root.left = n11;
//        root.right = n12;
//
//        n11.left = n21;
//        n11.right = n22;
//        n12.left = n23;
//        n12.right = n24;
//
//        n21.left = n31;
//        n21.right = n32;
//        n22.left = n33;
//        n22.right = n34;
//        n23.left = n35;
//        n23.right = n36;
//        n24.left = n37;
//        n24.right = n38;
    }

    public void printPaths() {
        int[] path = new int[1000];
        printPaths(root, path, 0);
    }

    /** 
    Recursive printPaths helper -- given a node, and an array containing 
    the path from the root node up to but not including this node, 
    prints out all the root-leaf paths. 
     */
    private void printPaths(Node node, int[] path, int pathLen) {
        if (node == null) {
            return;
        }

        // append this node to the path array 
        path[pathLen] = node.data;
        pathLen++;

        // it's a leaf, so print the path that led to here 
        if (node.left == null && node.right == null) {
            printArray(path, pathLen);
        } else {
            // otherwise try both subtrees 
            printPaths(node.left, path, pathLen);
            printPaths(node.right, path, pathLen);
        }
    }

    /** 
    Utility that prints ints from an array on one line. 
     */
    private void printArray(int[] ints, int len) {
        int i;
        for (i = 0; i < len; i++) {
            System.out.print(ints[i] + " ");
        }
        System.out.println();
    }

    public boolean hasPathSum(int sum) {
        return (hasPathSum(root, sum));
    }

    boolean hasPathSum(Node node, int sum) {
        // return true if we run out of tree and sum==0 
        if (node == null) {
            return (sum == 0);
        } else {
            // otherwise check both subtrees 
            int subSum = sum - node.data;
            return (hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
        }
    }
    
   

public boolean isBST2() { 
 return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) ); 
}
/** 
  Efficient BST helper -- Given a node, and min and max values, 
  recurs down the tree to verify that it is a BST, and that all 
  its nodes are within the min..max range. Works in O(n) time -- 
  visits each node only once. 
*/ 
private boolean isBST2(Node node, int min, int max) { 
  if (node==null) { 
      System.out.println("true");
    return(true); 
  } 
  else { 
   // left should be in range  min...node.data 
    boolean leftOk = isBST2(node.left, min, node.data);

    // if the left is not ok, bail out 
    if (!leftOk){
        System.out.println("false");
        return(false);
        
    }

    // right should be in range node.data+1..max 
    boolean rightOk = isBST2(node.right, node.data+1, max);

    return(rightOk); 
  } 
} 

    public static void main(String[] args) {
        
        InToPost iTP = new InToPost("A - 2 * A * B + B / A - B");
        iTP.doTrans();
        
        
//          Scanner        console = new Scanner(System.in);
//       ExpressionTree calc ;
//        
//       
//     
//    
//
//   // Allow for a command-line argument (which would be double-quoted).
//      if ( args.length > 0 )
//      {
//         System.out.println ("Processing string " + args[0]);
//
//         calc = new ExpressionTree(new Scanner(args[0]));
//      }
//      else
//      {
//         System.out.println
//           ( "Prefix expression, with all elements separated by blanks");
//
//         calc = new ExpressionTree(new Scanner(console.nextLine()));
//      }
//
//      System.out.println ("\nInput as prefix expression:");
//      calc.showPreFix();
//
//      System.out.println ("\nInput as postfix expression:");
//      calc.showPostFix();
//
//      System.out.println ("\nInput as parenthesized infix expression:");
//      calc.showInFix();
//
//      System.out.println ("\nValue:  " + calc.evaluate());
//
//      System.out.print ("Press <Enter> to exit:  ");
//      console.nextLine();
      
      
//        Expression expr = new Expression();
//        expr.build123b();
////        expr.insert(10);
////        expr.insert(2);
////        expr.insert(7);
////        expr.insert(8);
////        expr.insert(11);
////        expr.insert(4);
//        expr.printPostorder();
////        Node n41 = null;
////        
////        Node root = new Node(2);
////        Node n11 = new Node(7);
////        Node n12 = new Node(5);
////        Node n21 = new Node(2);
////        Node n22 = new Node(6);
////        Node n23 = new Node(3);
////        Node n24 = new Node(6);
////        Node n31 = new Node(5);
////        Node n32 = new Node(8);
////        Node n33 = new Node(4);
////        Node n34 = new Node(5);
////        Node n35 = new Node(8);
////        Node n36 = new Node(4);
////        Node n37 = new Node(5);
////        Node n38 = new Node(8);
////        n41 = new Node(10);
//////        expr.insert(n41, 10);
////
////
////        root.left = n11;
////        root.right = n12;
////
////        n11.left = n21;
////        n11.right = n22;
////        n12.left = n23;
////        n12.right = n24;
////
////        n21.left = n31;
////        n21.right = n32;
////        n22.left = n33;
////        n22.right = n34;
////        n23.left = n35;
////        n23.right = n36;
////        n24.left = n37;
////        n24.right = n38;
////        
////        n31.right = n41;
////       
////     
//       // expr.hasPathSum(4);
//        expr.printPaths();
//        //expr.isBST2();
//        //expr.lookup(4);


//         2               
//        / \       
//       /   \      
//      /     \     
//     /       \    
//     7       5       
//    / \     / \   
//   /   \   /   \  
//   2   6   3   6   
//  / \ / \ / \ / \ 
//  5 8 4 5 8 4 5 8 
//   \
//    10
    }
}
